package com.sicheng.蓝桥.练习题.线段树.动态开点;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/5/26 12:43
 */
@SuppressWarnings("all")
public class 毯子覆盖 {
    //https://leetcode.cn/problems/maximum-white-tiles-covered-by-a-carpet/

    static class Tree {
        int ls;
        int rs;
        int w;
        int lazy;
    }

    int N = (int) 1e9;
    int M = (int) 1e6;
    Tree[] tree = new Tree[5 * M];
    int cnt = 1;

    void lazyCreate(int st) {
        if (tree[st] == null) {
            tree[st] = new Tree();
        }
        if (tree[st].ls == 0) {
            tree[st].ls = ++cnt;
            tree[tree[st].ls] = new Tree();
        }
        if (tree[st].rs == 0) {
            tree[st].rs = ++cnt;
            tree[tree[st].rs] = new Tree();
        }
    }


    void update(int l, int r) {
        update(l, r, 1, 1, N);
    }

    void update(int l, int r, int st, int ll, int rr) {

        lazyCreate(st);
        if (tree[st].lazy == 1)
            return;
        if (l == ll && r == rr) {
            tree[st].lazy = 1;
            tree[st].w = r - l + 1;
            return;
        }

        int mid = ll + rr >> 1;
        if (r <= mid) {
            update(l, r, tree[st].ls, ll, mid);
        } else if (l > mid) {
            update(l, r, tree[st].rs, mid + 1, rr);
        } else {
            update(l, mid, tree[st].ls, ll, mid);
            update(mid + 1, r, tree[st].rs, mid + 1, rr);
        }
        pushUp(st);
    }

    int query(int l, int r) {
        return query(l, r, 1, 1, N);
    }

    int query(int l, int r, int st, int ll, int rr) {
        lazyCreate(st);
        if (tree[st].lazy == 1) {
            return r - l + 1;
        }

        if (l == ll && r == rr) {
            return tree[st].w;
        }

        int res = 0;

        int mid = ll + rr >> 1;
        if (r <= mid) {
            res += query(l, r, tree[st].ls, ll, mid);
        } else if (l > mid) {
            res += query(l, r, tree[st].rs, mid + 1, rr);
        } else {
            res += query(l, mid, tree[st].ls, ll, mid);
            res += query(mid + 1, r, tree[st].rs, mid + 1, rr);
        }
        return res;
    }


    void pushUp(int st) {
        tree[st].w = tree[tree[st].ls].w + tree[tree[st].rs].w;
    }

    public int maximumWhiteTiles(int[][] tiles, int carpetLen) {

        Arrays.sort(tiles, Comparator.comparingInt(e -> e[0]));
        for (int[] tile : tiles) {
            update(tile[0], tile[1]);
        }

        int max = 0;
        for (int[] tile : tiles) {
            int r = carpetLen + tile[0] - 1;
            r = r > N ? N : r;
            max = Math.max(query(tile[0], r), max);
            if (max == carpetLen || N - tile[0] < max)
                break;
        }

        return max;
    }


    public static void main(String[] args) {

        //tiles = [[1,5],[10,11],[12,18],[20,25],[30,32]], carpetLen = 10
        毯子覆盖 solution = new 毯子覆盖();
        int[][] tiles = {
                {1, 1},
                {99999, 99999}
        };
        int carpetLen = 1638;
        System.out.println(solution.maximumWhiteTiles(tiles, carpetLen));
    }
}
